﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace Snowdreamist.Collection.Tree
{
    public class TreeNodeNavigator<T> : ITreeNodeNavigator<T> where T : ITreeNode<T>
    {
        public TreeNodeNavigator(T treeNode)
        {
            if (treeNode == null)
                throw new ArgumentNullException("treeNode");

            this.Current = treeNode;
        }

        public T Current { get; private set; }

        public virtual bool MoveDown()
        {
            if (this.Current.Children.Count == 0)
                return false;
            this.Current = this.Current.Children[0];
            return true;
        }

        public virtual bool MoveUp()
        {
            if (this.Current.Parent == null)
                return false;
            this.Current = this.Current.Parent;
            return true;
        }

        public virtual bool MovePrev()
        {
            if (this.Current.Parent == null)
                return false;
            var index = this.Current.Parent.Children.IndexOf(this.Current);
            if (index < 1)
                return false;
            this.Current = this.Current.Parent.Children[index - 1];
            return true;
        }

        public virtual bool MoveNext()
        {
            if (this.Current.Parent == null)
                return false;
            var index = this.Current.Parent.Children.IndexOf(this.Current);
            if (index >= this.Current.Parent.Children.Count - 1)
                return false;
            this.Current = this.Current.Parent.Children[index + 1];
            return true;
        }

        public bool MoveTo(T treeNode)
        {
            // check if the two nodes are from the same root
            if (!this.Current.IsSameRoot(treeNode))
                return false;
            this.Current = treeNode;
            return true;
        }

        public virtual T AppendChild(T treeNode)
        {
            this.Current.Children.Add(treeNode);
            return treeNode;
        }

        public virtual T AppendAfter(T treeNode)
        {
            if (this.Current.Parent == null)
                throw new InvalidOperationException();
            var index = this.Current.Parent.Children.IndexOf(this.Current);
            if (index == -1)
                throw new InvalidOperationException();
            this.Current.Parent.Children.Insert(index + 1, treeNode);
            return treeNode;
        }

        public virtual T AppendBefore(T treeNode)
        {
            if (this.Current.Parent == null)
                throw new InvalidOperationException();
            var index = this.Current.Parent.Children.IndexOf(this.Current);
            if (index == -1)
                throw new InvalidOperationException();
            this.Current.Parent.Children.Insert(index, treeNode);
            return treeNode;
        }

        public T AppendChildAndMoveTo(T treeNode)
        {
            this.AppendChild(treeNode);
            this.Current = treeNode;
            return treeNode;
        }

        public T AppendAfterAndMoveTo(T treeNode)
        {
            this.AppendAfter(treeNode);
            this.Current = treeNode;
            return treeNode;
        }

        public T AppendBeforeAndMoveTo(T treeNode)
        {
            this.AppendBefore(treeNode);
            this.Current = treeNode;
            return treeNode;
        }

        public ITreeNodeDeepFirstTraverseIterator<T> DeepFirstTraverse(DeepFirstTraverseMode mode)
        {
            return new TreeNodeDeepFirstTraverseIterator(mode, this);
        }

        public ITreeNodeIterator<T> BreadFirstTraverse()
        {
            return new TreeNodeBreadFirstTraverseIterator(this);
        }

        #region private

        private class IterationWrapper
        {
            public IterationWrapper(T value)
            {
                this.Value = value;
                this.IsExpanded = false;
            }

            public T Value { get; set; }

            public bool IsExpanded { get; set; }
        }

        private class TreeNodeDeepFirstTraverseIterator : ITreeNodeDeepFirstTraverseIterator<T>
        {
            public TreeNodeDeepFirstTraverseIterator(DeepFirstTraverseMode mode, TreeNodeNavigator<T> navigator)
            {
                if (mode == DeepFirstTraverseMode.Inorder)
                    throw new NotSupportedException();
                this._navigator = navigator;
                this.Mode = mode;
            }

            public DeepFirstTraverseMode Mode { get; private set; }

            public IEnumerator<T> GetEnumerator()
            {
                Stack<IterationWrapper> stack = new Stack<IterationWrapper>();
                stack.Push(new IterationWrapper(this._navigator.Current));
                while (stack.Count != 0)
                {
                    switch (this.Mode)
                    {
                        default:
                            throw new NotSupportedException();

                        case DeepFirstTraverseMode.Preorder:
                            {
                                var node = stack.Pop();
                                // return current node
                                yield return node.Value;
                                // check children
                                if (node.Value.Children.Count != 0)
                                {
                                    // expand node
                                    node.IsExpanded = true;
                                    foreach (var n in node.Value.Children.Reverse())
                                        stack.Push(new IterationWrapper(n));
                                }
                            }
                            break;

                        case DeepFirstTraverseMode.Postorder:
                            {
                                var node = stack.Peek();
                                // check children
                                if (!node.IsExpanded && node.Value.Children.Count != 0)
                                {
                                    // expand node
                                    node.IsExpanded = true;
                                    foreach (var n in node.Value.Children.Reverse())
                                        stack.Push(new IterationWrapper(n));
                                }
                                else
                                {
                                    // return
                                    stack.Pop();
                                    yield return node.Value;
                                }
                            }
                            break;
                    }
                }
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.GetEnumerator();
            }

            private TreeNodeNavigator<T> _navigator;
        }

        private class TreeNodeBreadFirstTraverseIterator : ITreeNodeIterator<T>
        {
            public TreeNodeBreadFirstTraverseIterator(TreeNodeNavigator<T> navigator)
            {
                this._navigator = navigator;
            }

            public IEnumerator<T> GetEnumerator()
            {
                Queue<T> queue = new Queue<T>();

                queue.Enqueue(this._navigator.Current);

                while (queue.Count != 0)
                {
                    // return
                    var node = queue.Dequeue();
                    yield return node;
                    // enqueue
                    if (node.Children.Count != 0)
                        foreach (var child in node.Children)
                            queue.Enqueue(node);
                }
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.GetEnumerator();
            }

            private TreeNodeNavigator<T> _navigator;
        }

        #endregion private
    }
}